#include <cstddef>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode()
      : val(0), left(nullptr), right(nullptr){} * TreeNode(int x)
      : val(x),
        left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};
void PreOrder(TreeNode *root, vector<TreeNode *> &nodes) {
  if (root == nullptr) {
    return;
  }
  nodes.push_back(root);
  PreOrder(root->left, nodes);
  PreOrder(root->right, nodes);
}
// 先序遍历 根左右
void flatten(TreeNode *root) {
  vector<TreeNode *> nodes;
  PreOrder(root, nodes);
  for (int i = 0; i < nodes.size() - 1; ++i) {
    nodes[i]->left = nullptr;
    nodes[i]->right = nodes[i];
  }
  nodes.back()->left = nullptr;
  nodes.back()->right = nullptr;
}

// 优化空间
void flatten_(TreeNode *root) {
  while (root != nullptr) {
    TreeNode *left = root->left;
    TreeNode *right = root->right;
    if (left != nullptr) {
      root->left = nullptr;
      root->right = left;
      if (right != nullptr) {
        // 找到当前节点最优节点
        TreeNode *t = root->right;
        while (t->right != nullptr) {
          t = t->right;
        }
        t->right = right;
      }
    }
    root = root->right;
  }
}